πŸ‘©β€πŸ’» 17685. μžλ™μ™„μ„±

@Seongukbaek Posted May 27, 2022 Β· Updated May 27, 2022 Β· 2 min read

문제

Programmers - μžλ™μ™„μ„±

πŸ“ Logic

public void insert(String word) { TrieNode thisNode = this.rootNode; for (int i = 0; i < word.length(); i++) { thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode()); thisNode.size++; } }
  • 단어λ₯Ό ν•œ κΈ€μžμ”© Trie 에 μΆ”κ°€ν•œλ‹€.

    • μ΄λ•Œ λžŒλ‹€μ‹μ„ μ΄μš©ν•˜μ—¬ μΆ”κ°€ν•˜λ„λ‘ ν•œλ‹€.
  • μΆ”κ°€ν•  λ•Œλ§ˆλ‹€, ν•΄λ‹Ή 단어가 μ‚¬μš©λ˜λŠ” 횟수λ₯Ό μ¦κ°€μ‹œν‚¨λ‹€. (go, gone, guild 의 경우, g 의 size λŠ” 3이닀.)
public int findCount(String word) { TrieNode thisNode = this.rootNode; int count = 0; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); TrieNode node = thisNode.getChildNodes().get(c); count++; if (node.size == 1) break; thisNode = node; } return count; }
  • μ£Όμ–΄μ§„ λ‹¨μ–΄μ˜ Trie λ₯Ό νƒμƒ‰ν•˜λ©΄μ„œ, size κ°€ 1인 κ²½μš°κΉŒμ§€ count λ₯Ό μ¦κ°€μ‹œν‚¨λ‹€.

    • size κ°€ 1μ΄λΌλŠ” 것은 κ²°κ΅­ ν•΄λ‹Ή 문자λ₯Ό μ‚¬μš©ν•˜λŠ” 단어가 1개인 경우이고, ν•΄λ‹Ή λ¬ΈμžκΉŒμ§€ μž…λ ₯ν•œλ‹€λ©΄ κ·Έ 단어λ₯Ό μžλ™μ™„μ„±μ‹œν‚¬ 수 μžˆλ‹€!

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class TrieNode { private Map<Character, TrieNode> childNodes = new HashMap<>(); int size; public Map<Character, TrieNode> getChildNodes() { return this.childNodes; } } class Trie { private TrieNode rootNode; public Trie() { rootNode = new TrieNode(); } public void insert(String word) { TrieNode thisNode = this.rootNode; for (int i = 0; i < word.length(); i++) { thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode()); thisNode.size++; } } public int findCount(String word) { TrieNode thisNode = this.rootNode; int count = 0; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); TrieNode node = thisNode.getChildNodes().get(c); count++; if (node.size == 1) break; thisNode = node; } return count; } } class Solution { public int solution(String[] words) { Trie t = new Trie(); for (String word : words) t.insert(word); int answer = 0; for (String word : words) answer += t.findCount(word); return answer; } }

✏️ Review

  • 처음 λ³΄λŠ” Trie λ¬Έμ œμ—¬μ„œ, 이 자료 ꡬ쑰λ₯Ό μ΄ν•΄ν•˜λŠ” 데 μ§‘μ€‘ν–ˆλ‹€. 마침 이번 μ£Ό CS μŠ€ν„°λ”” λ‚΄μš© 쀑 Trie κ°€ μžˆμ–΄μ„œ λ¨Όμ € μ •λ¦¬ν•œ ν›„ κ΅¬ν˜„ν•΄λ³΄μ•˜λ‹€.
  • 생각보닀 많이 μ–΄λ €μš΄ λ‚΄μš©μ€ μ•„λ‹ˆμ—ˆλ˜ 것 κ°™μ§€λ§Œ, μ‘μš©ν•΄μ„œ 문제λ₯Ό ν‘ΈλŠ” λ°λŠ” μ’€ κ±Έλ Έλ‹€.
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€